package com.itheima.busi;

import java.util.Arrays;

public class Topk {

    //堆元素下沉，形成最小堆，序号从i开始
    static void down(int[] nodes,int i) {
        //顶点序号遍历，只要到1半即可，时间复杂度为O(log2n)
        while ( i << 1  <  nodes.length){
            //左子，为何左移1位？回顾一下二叉树序号
            int left = i<<1;
            //右子，左+1即可
            int right = left+1;
            //标记，指向 本节点，左、右子节点里最小的，一开始取i自己
            int flag = i;
            //判断左子是否小于本节点
            if (nodes[left] < nodes[i]){
                flag = left;
            }
            //判断右子
            if (right < nodes.length && nodes[flag] > nodes[right]){
                flag = right;
            }
            //两者中最小的与本节点不相等，则交换
            if (flag != i){
                int temp = nodes[i];
                nodes[i] = nodes[flag];
                nodes[flag] = temp;
                i = flag;
            }else {
                //否则相等，堆排序完成，退出循环即可
                break;
            }
        }

    }

    public static void main(String[] args) {
        //原始数据
        int[] src={3,6,2,7,4,8,1,9,2,5};
        System.out.println("原始数据："+Arrays.toString(src));
        //要取几个
        int k = 5;
        //堆，为啥是k+1？请注意，最小堆的0是无用的，序号从1开始
        int[] nodes = new int[k+1];
        //取前k个数，注意这里只是个二叉树，还不满足最小堆的要求
        for (int i = 0; i < k; i++) {
            nodes[i+1]=src[i];
        }
        System.out.println("截取k入堆:"+Arrays.toString(nodes));
        //从最底的子树开始，堆顶下沉
        //这里才真正的形成最小堆
        for (int i = k>>1; i >= 1; i--) {
            down(nodes,i);
        }
        System.out.println("形成最小堆:"+Arrays.toString(nodes));

        //把余下的n-k个数，放到堆顶，依次下沉，topk堆算法的开始
        for (int i = src.length - k;i<src.length;i++){
            if (nodes[1] < src[i]){
                nodes[1] = src[i];
                down(nodes,1);
            }
        }
        System.out.println("最终topk:"+Arrays.toString(nodes));
    }
}
